package com.future;

/**
 * Description: 1277. 统计全为 1 的正方形子矩阵
 *
 * @author weiruibai.vendor
 * Date: 2022/7/6 15:12
 */
public class Solution_1277 {

    public static void main(String[] args) {
        int[][] grid = new int[][]{
                {1, 1, 1, 1, 1, 0},
                {1, 0, 0, 1, 0, 1},
                {1, 0, 1, 1, 1, 1},
                {0, 1, 1, 1, 1, 1}};
       /* grid = new int[][]{
                {1, 1, 1, 1, 1, 1, 1, 1},
                {1, 1, 1, 1, 0, 1, 1, 0},
                {1, 1, 0, 1, 1, 1, 1, 0},
                {1, 1, 1, 1, 1, 0, 0, 0},
                {1, 1, 1, 1, 1, 0, 0, 0}};*/
        /*grid = new int[][]{
                {1, 1, 0, 1},
                {1, 1, 0, 1},
                {1, 1, 1, 1}
        };*/
        grid = new int[][]{
                {0, 1, 1, 1},
                {1, 1, 1, 1},
                {0, 1, 1, 1}
        };
        /*grid = new int[][]{
                {1, 0, 1},
                {1, 1, 0},
                {1, 1, 0}
        };
        grid = new int[][]{
                {0, 0, 0, 1, 0, 1, 0},
                {0, 1, 0, 0, 0, 0, 0},
                {0, 1, 0, 1, 0, 0, 1},
                {0, 0, 1, 1, 0, 0, 1},
                {1, 1, 1, 1, 1, 1, 0},
                {1, 0, 0, 1, 0, 1, 1},
                {0, 1, 0, 0, 1, 0, 1},
                {1, 1, 0, 1, 1, 1, 0},
                {1, 0, 1, 0, 1, 0, 1},
                {1, 1, 1, 0, 0, 0, 0}
        };
        grid = new int[][]{
                {1, 1, 0, 0, 1},
                {1, 0, 1, 1, 1},
                {1, 1, 1, 1, 1},
                {1, 0, 1, 0, 1},
                {0, 0, 1, 0, 1}
        };*/
        System.out.println(countSquares(grid));
    }

    public static int countSquares(int[][] matrix) {
        int N = matrix.length;
        int M = matrix[0].length;
        int[][] rightArr = new int[N][M];
        for (int i = 0; i < N; i++) {
            rightArr[i][M - 1] = matrix[i][M - 1];
            for (int j = M - 2; j >= 0; j--) {
                rightArr[i][j] = matrix[i][j] == 1 ? rightArr[i][j + 1] + 1 : 0;
            }
        }
        int[][] downArr = new int[N][M];
        for (int i = 0; i < M; i++) {
            downArr[N - 1][i] = matrix[N - 1][i];
            for (int j = N - 2; j >= 0; j--) {
                downArr[j][i] = matrix[j][i] == 1 ? downArr[j + 1][i] + 1 : 0;
            }
        }
        //
        int max = 0;
        int ans = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (matrix[i][j] == 1) {
                    /**
                     * (i,j)   (i,j_right)
                     * (i_down,j)   (i_down,j_right)
                     */
                    int j_right = rightArr[i][j];
                    int i_down = downArr[i][j];
                    int border = Math.min(j_right, i_down);
                    for (int k = i; k < i + border; k++) {
                        if (border > rightArr[k][j]) {
                            /**
                             * 重点！！
                             * 可能遍历到k时，突然断崖式的变小，这是除了第k行，i...k-1所处的高度可能大于rightArr[k][j]
                             * eg:
                             * grid = new int[][]{
                             *                 {1, 1, 0, 0, 1},
                             *                 {1, 0, 1, 1, 1},
                             *                 {1, 1, 1, 1, 1},
                             *                 {1, 0, 1, 0, 1},
                             *                 {0, 0, 1, 0, 1}
                             *         }
                             */

                            border = Math.max(rightArr[k][j], k - i);
                        }
                    }
                    //System.out.println("max :" + (max = Math.max(border, max)));
                    ans += border;
                }
            }
        }
        return ans;
    }

}
